#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/7 19:59
# @USER    : Shengji He
# @File    : WorldLadder2.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict, deque
from typing import List


class Solution:
    def __init__(self):
        self.__res_dict = {}

    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        """
        Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation
        sequence(s) from beginWord to endWord, such that:
            - Only one letter can be changed at a time

            - Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

        Note:
            - Return an empty list if there is no such transformation sequence.
            - All words have the same length.
            - All words contain only lowercase alphabetic characters.
            - You may assume no duplicates in the word list.
            - You may assume beginWord and endWord are non-empty and are not the same.
        Example 1:
            Input:
                beginWord = "hit",

                endWord = "cog",

                wordList = ["hot","dot","dog","lot","log","cog"]

            Output:
            [
              ["hit","hot","dot","dog","cog"],

              ["hit","hot","lot","log","cog"]

            ]
        Example 2:
            Input:
                beginWord = "hit"

                endWord = "cog"

                wordList = ["hot","dot","dog","lot","log"]

            Output: []

            Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

        :param beginWord: str
        :param endWord: str
        :param wordList: List[str]
        :return: List[List[str]]
        """
        # ans = []
        # if endWord not in wordList:
        #     return ans
        # wordList = list(set(wordList))
        # if beginWord in wordList:
        #     wordList.remove(beginWord)
        # if len(beginWord) == 1 or (len(beginWord) - sum([i == j for i, j in zip(list(beginWord), list(endWord))]) == 1):
        #     self.__res_dict[beginWord] = [[beginWord, endWord]]
        #     return [[beginWord, endWord]]
        # s = 0
        # maxlength = len(wordList) + 1
        # while s < len(beginWord):
        #     if beginWord[s] == endWord[s]:
        #         s += 1
        #         continue
        #     for i in range(len(wordList)):
        #         ele = wordList[i]
        #         if beginWord[:s] + beginWord[s + 1:] == ele[:s] + ele[s + 1:]:
        #             if self.__res_dict.get(ele):
        #                 temp = self.__res_dict.get(ele)
        #             else:
        #                 temp = self.findLadders(ele, endWord, wordList[: i] + wordList[i + 1:])
        #             for t in temp:
        #                 output = [beginWord]
        #                 output.extend(t)
        #                 if output[-1] == endWord:
        #                     if len(output) < maxlength:
        #                         ans = [output]
        #                         maxlength = len(output)
        #                     elif len(output) == maxlength:
        #                         ans.append(output)
        #                     else:
        #                         pass
        #     s += 1
        # self.__res_dict[beginWord] = ans
        # return ans
        if endWord not in wordList:
            return []
        wordList.append(beginWord)
        wordList = list(set(wordList))
        if len(beginWord) == 1 or (len(beginWord) - sum([i == j for i, j in zip(list(beginWord), list(endWord))]) == 1):
            self.__res_dict[beginWord] = [[beginWord, endWord]]
            return [[beginWord, endWord]]
        # 构建具有邻接关系的桶
        buckets = defaultdict(list)
        for word in wordList:
            for i in range(len(beginWord)):
                match = word[:i] + '_' + word[i + 1:]
                buckets[match].append(word)

        # BFS遍历
        preWords = defaultdict(list)  # 前溯词列表
        toSeen = deque([(beginWord, 1)])  # 待遍历词及深度列表
        beFound = {beginWord: 1}  # 已探测词词列表
        while toSeen:
            curWord, level = toSeen.popleft()
            for i in range(len(beginWord)):
                match = curWord[:i] + '_' + curWord[i + 1:]
                for word in buckets[match]:
                    if word not in beFound:
                        beFound[word] = level + 1
                        toSeen.append((word, level + 1))
                    # 当前深度等于该词首次遍历深度，则仍应加入前溯词列表
                    if beFound[word] == level + 1:
                        preWords[word].append(curWord)
            # 已搜索到目标词，且完成当前层遍历
            if endWord in beFound and level + 1 > beFound[endWord]:
                break
        # 列表推导式输出结果
        if endWord in beFound:
            res = [[endWord]]
            while res[0][0] != beginWord:
                res = [[word] + r for r in res for word in preWords[r[0]]]
            return res
        else:
            return []


if __name__ == '__main__':
    # beginWord = "hit"
    # endWord = "cog"
    # wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    # beginWord = "hot"
    # endWord = "dog"
    # wordList = ["hot", "dog", "dot"]
    beginWord = "qa"
    endWord = "sq"
    wordList = ["si", "go", "se", "cm", "so", "ph", "mt", "db", "mb", "sb", "kr", "ln", "tm", "le", "av", "sm", "ar",
                "ci", "ca", "br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya", "cr", "po", "fe", "ho", "ma",
                "re", "or", "rn", "au", "ur", "rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if", "pb", "ge",
                "th", "pm", "rb", "sh", "co", "ga", "li", "ha", "hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh",
                "wm", "an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn", "mi", "am", "ex", "pt", "io", "be",
                "fm", "ta", "tb", "ni", "mr", "pa", "he", "lr", "sq", "ye"]
    S = Solution()
    print(S.findLadders(beginWord, endWord, wordList))
    print('done')
